package cn.edu.zufe.mjt.hash;

import cn.edu.zufe.mjt.validator.Validator;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * 序列二元组等式问题
 * 小红有一个长为 n 的序列 p，她想知道 p 中有多少个 i，j，满足 i < j，且 p[i] + p[j] = i + j。
 * 两个输入，n 表示排列的长度 （1 ≤ n ≤ 2*10^6），p 表示序列。
 * 问题关键：确定 j 的位置之后，问题转化为在 j-1 号前缀中寻找符合条件的 i。
 */
public class SequenceBinaryEquationQuestions {
    public static void main(String[] args) {
        int[] ints = Validator.randomArray(5, 5);
        System.out.println(Arrays.toString(ints));
        System.out.println(countBinaryEquation(ints));
    }


    public static int countBinaryEquation(int[] p) {
        // [2,1,3,5,4] 下标从 1 开始
        // i+j = p[i] + p[j]  假设 j = 5， i + 5 = p[i] + p[5]
        // p[i] - i = 5 - p[5] = 1，此时问题九转化成了在 [2,1,3,5] 中寻找满足 p[i] - i = 1 的 i 的个数
        // 可以对4号前缀建立一个 p[i] - i 的map，查询 map[1] 即可
        int sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 1; i <= p.length; i++) {
            sum += map.getOrDefault(i - p[i-1], 0);
            map.put(p[i-1] - i , map.getOrDefault(p[i-1] - i, 0) + 1);
        }
        return sum;
    }
}
